package com.mdnote.practice.generic_recursion;

import java.util.LinkedList;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/15
 * @description 翻转二叉树
 */
public class LeetCode226 {

    public static void main(String[] args) {
        LeetCode226 leetCode226 = new LeetCode226();
        TreeNode root = new TreeNode(10);
        root.left = new TreeNode(5);
        root.right = new TreeNode(15);
        root.left.left = new TreeNode(2);
        leetCode226.invertTree(root);
    }

    public TreeNode invertTree(TreeNode root) {
        // recursion
        recursion(root);
        // for loop
        forLeep(root);
        return root;
    }


    private void forLeep(TreeNode node) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            TreeNode tempNode = queue.removeFirst();
            // swap
            TreeNode temp = tempNode.left;
            tempNode.left = tempNode.right;
            tempNode.right = temp;
            // add child
            if (tempNode.left != null) {
                queue.add(tempNode.left);
            }
            if (tempNode.right != null) {
                queue.add(tempNode.right);
            }
        }
    }

    private void recursion(TreeNode node) {
        // Terminator
        if (node == null || (node.left == null && node.right == null)) {
            return;
        }
        // process current logic
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;
        // drill down
        recursion(node.left);
        recursion(node.right);
        // restore current data
    }


    public static class TreeNode {
         int val;
         TreeNode left;
         TreeNode right;
         TreeNode(int x) { val = x; }
     }

}
